1. Field of the Invention
The present invention is related to information handling systems for displaying graphics images on raster display devices and more particularly to graphics display systems for generating and displaying images based upon hierarchical graphics data structures. This invention more particularly relates to apparatus and methods for managing memory in a graphics display system for displaying hierarchical data structures.
2. Background of the Invention
Graphics display systems are designed to interpret graphics commands issued by an application program to create a graphics image for display on a display device. Early graphics display systems each had unique interfaces and the application programs were required to recognize and program to those unique interfaces. More recently several graphics interface standards have evolved. For example, a Graphics Kernel Standard (GKS), Programmer's Hierarchical Interactive Graphics Systems (PHIGS) and CGI each provide a standard method for linking applications programs and graphics systems. A consistent interface frees the application program of the burden of developing multiple and different interfaces to various hardware systems. The application programmer can therefore focus more attention on providing features and performance in his specific graphics application.
Several recent graphics standards use multi-level or hierarchical databases to contain the graphics models. This powerful concept minimizes data replication in graphics models and facilitates interactive modification and transformation of data. Graphics structures or models can be defined once and then referenced as many times as necessary to create the final object.
The basic building block of the hierarchical graphics interface is the structure. The structures contain graphics elements such as drawing primitives (e.g., lines, characters, polygons), attribute selections (color), modelling transformations, labels, and viewing selections. Structures specify the sequence of elements that, when processed, generate a specific effect on the screen. In a hierarchical graphics environment, structures execute other structures which, in turn, can execute other structures. This creates a tree-like hierarchy where primitive structures can be repeatedly used throughout the drawing operation. Graphics scenes are created by traversing the structure tree and proceeding down through various levels of structure as defined in the hierarchical database.
FIG. 1 illustrates the structure hierarchy. Structure A 100 is composed of several primitives or drawing commands 102-114. Each of these primitives or commands is executed in order from left to right. The structure hierarchy is created through the use of "structure" commands. For example, command 106 directs the execution or inclusion of structure B at that point. Structure B(116) contains drawing primitives 118-124. Structure B may, in turn, request another structure, for example structure D(126), containing further drawing primitives. Upon the completion of all drawing primitives of structure D(126), control returns to the "structure" command 124. Since no further drawing primitives exist in structure B(116) control is returned to structure A to the command following "structure" command 106, i.e., 108. 108 in turn executes structure C (130). Structure E 132 is executed by structure C. As shown by command 114 structure C may be repetitively executed and included in different parts of the hierarchy.
The called or "child" structure inherits the attributes of the "parent" structure during the execute structure operation. The newly formed child structure continues to execute until it encounters another structure command or until it completes its list of display primitives or commands. When control is returned to the parent structure the previous parent structure state is returned and processing continues for the remaining structure elements. Thus the following actions occur when a "structure" command is encountered in a parent structure:
traversal of the parent structure is suspended PA1 the values of the parent structure are saved PA1 the child structure is traversed and completed PA1 the child structure returns control to the parent structure PA1 the parent structure state values are restored PA1 the parent structure traversal resumes.
Hierarchical graphic interfaces require that the entire state of the graphics context be saved when the structure call is initiated. The size of the graphic state can be 512 to 1024 32-bit words. A graphics processor must replicate the state in order to give the child structure the same attributes as the parent structure and must save the state for resumption of execution when the child structure is completed.
A standard 32-bit processor can perform the transfer using a read/write copy loop to transfer the structure state. A structure size of 512 entries being copied through a typical copy loop of 0.25-0.5 microseconds per iteration would require 128-256 microseconds to complete. Larger structures or slower processors would take considerably longer. The speed of the replication frequently becomes a major bottleneck in the ability of a graphics processor to efficiently execute a hierarchical graphics model.